import java.util.*;

public class Solution460 {
    /**
     * 请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。
     *
     * get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
     * put(key, value) - 如果键不存在，请设置或插入值。
     * 当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。
     * 在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近 最少使用的键。
     * 「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
     *
     */
    class LFUCache {
        class Node{
            int key, val, freq = 1;
            public Node(int key,int val) {
                this.key = key;
                this.val = val;
            }
        }

        int capacity;
        int size;
        int min;  //储存当前最小频次
        Map<Integer, Node> cache;
        Map<Integer, LinkedHashSet<Node>> frequency;

        public LFUCache(int capacity) {
            this.cache = new HashMap<>();
            this.frequency = new HashMap<>();
            this.capacity = capacity;
        }

        public int get(int key) {
            if (capacity == 0) return -1;
            if (cache.containsKey(key)){
                Node node = cache.get(key);
                freqInc(node);
                return node.val;
            } else {
                return -1;
            }
        }
        public void put(int key, int value) {
            if (capacity == 0) {
                return;
            }
            Node node = cache.get(key);
            if (node != null) {
                node.val = value;
                freqInc(node);
            } else {
                if (size == capacity) {
                    Node deadNode = removeNode();
                    cache.remove(deadNode.key);
                    size--;
                }
                Node newNode = new Node(key, value);
                cache.put(key, newNode);
                addNode(newNode);
                size++;
            }
        }

        public void freqInc(Node node){
            int freq = node.freq;
            LinkedHashSet<Node> set = frequency.get(freq);
            set.remove(node);
            if (freq == min && set.size() == 0){
                min = freq + 1;
            }
            node.freq++;
            LinkedHashSet<Node> newSet = frequency.get(freq + 1);
            if (newSet == null){
                newSet = new LinkedHashSet<>();
                frequency.put(freq + 1, newSet);
            }
            newSet.add(node);
        }

        public void addNode(Node node){
            LinkedHashSet<Node> set = frequency.get(1);
            if (set == null){
                set = new LinkedHashSet<>();
                frequency.put(1,set);
            }
            set.add(node);
            min = 1;
        }

        public Node removeNode(){
            LinkedHashSet<Node> set = frequency.get(min);
            Node deadNode = set.iterator().next();
            set.remove(deadNode);
            return deadNode;
        }
    }
}
